/*
递归：函数自身调用的语法技巧
递归主要有什么用：可以讲一些大型复杂的问题进行简化处理(代码少)
    将一个大的问题进行逐层的化小 变成一个较小的问题来处理
    无论怎么化小 每一层处理的逻辑必须一致
递归有风险：稍微不注意 就会导致栈内存溢出; 费时间
分治算法 回溯算法
递归一般分为三步：前进段、边界条件、返回段
所以注意 将来写递归 先考虑边界问题！！！
人用迭代 神用递归
*/
public class Recursion {
    public static void main(String[] args) {
        /*
        StackOverflowError 栈内存溢出错误/异常
        主要因为 函数的运行是基于栈内存的
        我们可以把每一个函数当成一个元素来看
        元素进栈与出栈的区别
        */
        //show();
        //show(5);
        //对1~100求和(迭代)
        int N = 100;
        int sum = 0;
        //O(n)
        for (int i = 1; i <= N; i++) {
            sum += i;
        }
        System.out.println(sum);
        //O(1)
        System.out.println(N * (N + 1) / 2);
        /*
        f(x)对1~x求和
        f(100) = f(99) + 100
        f(99) = f(98) + 99
        ...
        f(3) = f(2) + 3    1+2 + 3
        f(2) = f(1) + 2    1 + 2
        f(1) = 1
                1, x = 1
        f(x)
                f(x-1) + x, x > 1
        */
        sum = nSum(N);
        System.out.println(sum);

        /*斐波那契数列
        1 1 2 3 5 8 13 21 34 55 ...
        fibo(n)
        f(x) = f(x - 1) + f(x - 2)
        f(1) = 1
        f(2) = 1
                1, x==1 || x== 2
        f(x)
                f(x - 1) + f(x - 2), x > 2
        */
        //System.out.println(fibo01(50));
        //O(n)
        //System.out.println(fibo02(50));
        //O(n)
        System.out.println(fibo03(50));


        System.out.println(Integer.MAX_VALUE);
        System.out.println(Integer.MAX_VALUE + 1);

        //(1)返回数值 (2)结束函数/将函数出栈
        return;
    }

    //迭代处理
    private static int fibo03(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n - 1];
    }

    //剪枝：将重复的内容进行提前的存储 下次用到直接取 避免重复运算
    private static int[] arr = new int[1000];
    private static int fibo02(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        if (arr[n] == 0) {
            arr[n] = fibo02(n - 1) + fibo02(n - 2);
        }
        return arr[n];
    }

    private static int fibo01(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fibo01(n - 1) + fibo01(n - 2);
    }

    private static int nSum(int n) {
        if (n == 1) {
            return 1;
        }
        return nSum(n - 1) + n;
    }

    private static void show(int n) {
        //形式参数实际上是当前函数的内部变量 —— 局部变量
        System.out.println(n);
        if (n == 1) {
            return;
        }
        show(n - 1);
        return;
    }

    private static void show() {
        show();
    }
}